package com.dmall.play.interview.chapter09;

import java.util.ArrayList;
import java.util.List;

/**
 * 使用纯递归
 * 题目：给定一个三角形 triangle ，找出自顶向下的最小路径和。
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 */
public class Leetcode120V1 {

    private int minTotal = Integer.MAX_VALUE;

    public int minimumTotal(List<List<Integer>> triangle) {
        backTrack(triangle, 0, 0, 0);
        return minTotal;
    }

    private void backTrack(List<List<Integer>> triangle, int row, int col, int total) {
        if (row == triangle.size()) {
            minTotal = Math.min(minTotal, total);
            return;
        }
        total += triangle.get(row).get(col);
        backTrack(triangle, row + 1, col, total);
        backTrack(triangle, row + 1, col + 1, total);
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> item1 = new ArrayList<>();
        item1.add(2);
        List<Integer> item2 = new ArrayList<>();
        item2.add(3);
        item2.add(4);
        List<Integer> item3 = new ArrayList<>();
        item3.add(6);
        item3.add(5);
        item3.add(7);
        List<Integer> item4 = new ArrayList<>();
        item4.add(4);
        item4.add(1);
        item4.add(8);
        item4.add(3);
        triangle.add(item1);
        triangle.add(item2);
        triangle.add(item3);
        triangle.add(item4);

        Leetcode120V1 leetcode120 = new Leetcode120V1();
        System.out.println(leetcode120.minimumTotal(triangle));
    }
}
